/*Copyright (C) 2013-2020 LZE*/
#include<bits/stdc++.h>
#define INF 0x7fffffff
#define print for(int i=1;i<=point;i++)cout<<ans[i]<<" ";cout<<endl;
using namespace std;
typedef long long ll;
const int N=10010;
int node,line,s,e,f[N][N]={0},b[N]={0},ans[N]={0};
inline int rd() {
	int x=0;bool ntv=false;char c=getchar();
	while((c<'0'||c>'9')&&c!='-')c=getchar();if(c=='-')ntv=true;else x=(c^48);c=getchar();
	while(c>='0'&&c<='9') {x=x*10+(c^48);c=getchar();}return ntv?-x:x;
}
void dijkstra(int _s){
	//init
	b[_s]=1;//1=False 0=True
	for(int i=1;i<=node;i++){
		if(i==_s)continue;
		ans[i]=f[_s][i];
		if(ans[i]==0)ans[i]=INF;
	}
	ans[_s]=0;
	int k=0;ans[0]=INF;
	//main
//	print
	for(int i=1;i<node;i++){
		k=0;
		for(int j=1;j<=node;j++){
			if(!b[j]){
				if(ans[j]<ans[k]){
					k=j;
				}
			}
		}
		b[k]=1;
		for(int j=1;j<=node;j++){
			if(b[j])continue;
			if(f[k][j]!=0)
				ans[j]=min(ans[j],ans[k]+f[k][j]);
		}
//		print
	}
} 
int main() {
	node=rd();line=rd();s=rd();//e=rd();
	for(int i=1;i<=line;i++){
		int x,y,num;x=rd();y=rd();num=rd();
		if(f[x][y]!=0)f[x][y]=min(f[x][y],num);
		else f[x][y]=num;
	}
	dijkstra(s);
//	cout<<endl;
	for(int i=1;i<=node;i++)cout<<ans[i]<<" ";
	return 0;
}
/*
4 5 1
1 2 2
1 3 3
2 3 2
2 4 4
3 4 1
*/
